//  BinarySearchTree.h
//  test
//
//  Created by yfy on 2022/3/29.


#ifndef BinarySearchTree_h
#define BinarySearchTree_h

#include <iostream>
#include <cstdbool>
#include <algorithm>

template <class K>
struct BSTreeNode
{
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;

    BSTreeNode(const K& key)
        :_left(nullptr)
        ,_right(nullptr)
        ,_key(key)
    {}
};

template <class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
private:
    Node* _root = nullptr;

private:
    void _Inorder(Node* root)      //中序遍历-避免_root的暴露
    {
        if(root == nullptr)
        {
            return;
        }
        _Inorder(root->_left);
        std::cout << root->_key << " ";
        _Inorder(root->_right);
    }
    void _Destroy(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
    Node* _Copy(Node* root)
    {
        if(root == nullptr)
        {
            return nullptr;
        }
        Node* newRoot = new Node(root->_key);
        newRoot->_left = _Copy(root->_left);
        newRoot->_right = _Copy(root->_right);
        
        return newRoot;
    }
public:
    BSTree() = default;     //强制编译器生成默认构造
    
    BSTree(const BSTree<K>& t)
    {
        _root = _Copy(t._root);
    }
    
    BSTree<K>& operator=(BSTree<K> t)
    {
        std::swap(_root, t._root);
        return *this;
    }
    
    ~BSTree()
    {
        _Destroy(_root);
    }
    
    void Inorder()       //对外接口——插入节点
    {
        _Inorder(_root);
        std::cout << std::endl;
    }

    bool Insert(const K& key)
    {
        if(_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
        Node *cur = _root;
        Node *parent = nullptr;
        while(cur)
        {
            if(key > cur->_key)     //插入节点键值大于cur的键值，往右子树走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(key < cur->_key)      //插入节点键值小于cur的键值，往左子树走
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                //键值相等，默认不允许冗余
                return false;
            }
        }
        //找到了唯一的插入位置，必须要通过父节点来连接节点，不能直接把节点给cur，因为cur出了作用域会直接销毁
        if(key > parent->_key)
        {
            parent->_right = new Node(key);
        }
        else
        {
            parent->_left = new Node(key);
        }
        return true;
    }

    Node* Find(const K& key)
    {
        if(_root == nullptr)
        {
            return nullptr;
        }
        Node* cur = _root;
        while(cur)
        {
            if(cur->_key < key)
            {
                cur = cur->_right;
            }
            else if(cur->_key > key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }

    bool Erase(const K& key)
    {
        if(_root == nullptr)
        {
            return false;
        }
        Node* cur = _root;
        Node* parent = cur;
        while(cur)              //先找这个节点的位置
        {
            if(key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if(key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                //找到要删除的节点了：1、叶节点。2、单子节点。3、双子节点
                if(cur->_left == nullptr)
                {
                    if(cur == _root)
                    {
                        _root = cur->_right;    //如果删除节点是根节点，且左为空
                    }
                    else
                    {
                        if(cur == parent->_left)    //删除节点为父节点左孩子，且左孩子为空
                        {
                            //把右孩子连接到父节点的左边
                            parent->_left = cur->_right;
                        }
                        else                        //删除节点为父节点右孩子，且左孩子为空
                        {
                            //把右孩子连接到父节点的右边
                            parent->_right = cur->_right;
                        }
                    }
                    
                    delete cur;
                    return true;
                }
                else if(cur->_right == nullptr)
                {
                    if(cur == _root)
                    {
                        _root = cur->_left;
                    }
                    else
                    {
                        if(cur == parent->_left)
                        {
                            parent->_left = cur->_left;
                        }
                        else
                        {
                            parent->_right = cur->_left;
                        }
                    }
                   
                    delete cur;
                    return true;
                }
                else        //双子节点——找删除节点的左子树中最大的节点（或右子树中最小）进行替换，再删除节点
                {
                    Node* maxLeftParent = cur;
                    Node* maxLeft = cur->_left;
                    while(maxLeft->_right)
                    {
                        maxLeftParent = maxLeft;
                        maxLeft = maxLeft->_right;
                    }
                    cur->_key = maxLeft->_key;

                    //删除maxLeft节点——一定是它父节点的右节点?并不一定！
                    if(maxLeft == maxLeftParent->_left)
                    {
                        maxLeftParent->_left = maxLeft->_left;
                    }
                    else
                    {
                        maxLeftParent->_right = maxLeft->_left;
                    }

                    delete maxLeft;
                    return true;
                }
            }
        }
        return false;
    }
public:
    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }
    
    Node* FindR(const K& key)
    {
        return _FindR(_root, key);
    }
    
    bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

private:
    //递归版插入
    bool _InsertR(Node*& root, const K& key)    //这个引用十分巧妙，能将父子节点连接起来，从而不用再多使用一个参数
    {
        if(root == nullptr)
        {
            root = new Node(key);
            return true;
        }
        else
        {
            if(key > root->_key)
            {
                return _InsertR(root->_right, key);
            }
            else if(key < root->_key)
            {
                return _InsertR(root->_left, key);
            }
            else
            {
                return false;
            }
        }
    }
    
    //递归版查找
    Node* _FindR(Node* root, const K& key)
    {
        if(root == nullptr)
        {
            return nullptr;
        }
        else
        {
            if(key > root->_key)
            {
                return _FindR(root->_right, key);
            }
            else if(key < root->_key)
            {
                return _FindR(root->_left, key);
            }
            else
            {
                return root;
            }
        }
    }
    
    //递归版删除
    bool _EraseR(Node*& root, const K& key)
    {
        if(root == nullptr)
        {
            return false;
        }
        if(key > root->_key)
        {
            return _EraseR(root->_right, key);
        }
        else if(key < root->_key)
        {
            return _EraseR(root->_left, key);
        }
        else
        {
            //删除
            Node* del = root;
            if(root->_left == nullptr)
            {
                root = root->_right;
            }
            else if(root->_right == nullptr)
            {
                root = root->_left;
            }
            else
            {
                Node* minRight = root->_right;
                while(minRight->_left)
                {
                    minRight = minRight->_left;
                }
                root->_key = minRight->_key;
                return _EraseR(root->_right, minRight->_key);   //可以直接传入minRight节点删除吗？
            }
            delete del;
            return true;
        }
    }
    
};

#endif /* BinarySearchTree_h */

